package org.usmile.algorithms.huawei.acm;

import java.util.Arrays;
import java.util.Scanner;

public class _等和子数组最小和 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int m = sc.nextInt();
        Integer[] nums = new Integer[m];
        for (int i = 0; i < m; i++) {
            nums[i] = sc.nextInt();
        }
        Arrays.sort(nums, (o1, o2) -> o2 - o1);
        if (nums[0].equals(nums[m - 1])) {
            System.out.println(nums[0]);
        }

        System.out.println(getResult(nums, m));
    }

    public static int getResult(Integer[] nums, int bucketCount) {
        int sum = 0;
        for (Integer num : nums) {
            sum += num;
        }

        while (bucketCount > 0) {
            if (canPartitionMSubsets(nums, sum, bucketCount)) {
                return sum / bucketCount;
            }

            bucketCount--;
        }

        return sum;
    }

    public static boolean canPartitionMSubsets(Integer[] nums, int sum, int bucketCount) {
        if (sum % bucketCount != 0) {
            return false;
        }
        int bucketCapacity = sum / bucketCount;
        if (bucketCapacity < nums[0]) {
            return false;
        }

        //    while (link.get(0) == bucketCapacity) { // 此段代码可能越界
        int start = 0;
        while (start < nums.length && nums[start] == bucketCapacity) {
            start++;
            bucketCount--;
        }

        int[] buckets = new int[bucketCount];

        return partition(nums, start, buckets, bucketCapacity);
    }

    public static boolean partition(Integer[] nums, int start, int[] buckets, int bucketCapacity) {
        if (start == nums.length) {
            return true;
        }

        int select = nums[start];
        for (int i = 0; i < buckets.length; i++) {
            if (i > 0 && buckets[i] == buckets[i - 1]) {
                continue;
            }
            if (select + buckets[i] <= bucketCapacity) {
                buckets[i] += select;
                if (partition(nums, start + 1, buckets, bucketCapacity)) {
                    return true;
                }
                buckets[i] -= select;
            }
        }

        return false;
    }
}
